package leetcode;

public class MultiplyStrings {

	public static void main(String[] args) {
		String num1 = "999";
		String num2 = "999";
		MultiplyStrings object = new MultiplyStrings();
		System.out.println(object.multiply(num1, num2));
	}
	
	
	// Runtime: 51 ms
	public String multiply(String num1, String num2) {
        if(num1 == null || num2 == null || num1.length() <= 0 || num2.length() <= 0){
        	return "";
        }
        if(num1.equals("0") || num2.equals("0")){
        	return "0";
        }
        int length1 = num1.length();
        int length2 = num2.length();
        int carry = 0;
        int cur = 0;
        //分别用来存储0 ... 9相乘的结果
        StringBuilder[] map = new StringBuilder[10];
        map[0] = new StringBuilder();
        for(int j = 1; j <= 9; j++){
        	StringBuilder sb = new StringBuilder();
        	carry = 0;
        	for(int i = length1 - 1; i >= 0; i--){
        		cur = j * (num1.charAt(i) - '0') + carry;
        		carry = cur / 10;
        		sb.append( (char)(cur % 10 + '0'));
        	}
        	if(carry != 0){
        		sb.append((char)(carry + '0'));
        	}
        	map[j] = sb.reverse();
        }
        String curRes = "0";
        char[] chas = new char[length2];
        for(int i = length2 - 1, j = 0; i >= 0; i--, j++){
        	chas[j] = '0';
        	//还要在后面加上i个0
        	StringBuilder sBuilder = new StringBuilder(map[num2.charAt(i) - '0']);
        	curRes = addStrings(curRes, sBuilder.append(chas, 0, j).toString());
        	System.out.println("curRes: " + curRes);
        }
        return curRes;
    }
	
	//字符串相加
	public String addStrings(String num1, String num2) {
		if (num1 == null || num2 == null) {
			return "";
		}
		int length1 = num1.length();
		int length2 = num2.length();
		if (length1 == 0 || length2 == 0) {
			return length1 == 0 ? num2 : num1;
		}
		// 数组的低位存储低位
		char[] chas1 = new StringBuilder(num1).reverse().toString()
				.toCharArray();
		char[] chas2 = new StringBuilder(num2).reverse().toString()
				.toCharArray();
		int maxLength = Math.max(length1, length2);
		char[] chas = new char[maxLength];
		int carry = 0;
		for (int i = 0; i < maxLength; i++) {
			int res = (i >= length1 ? 0 : chas1[i] - '0')
					+ (i >= length2 ? 0 : chas2[i] - '0') + carry;
			chas[i] = (char) (res % 10 + '0');
			carry = res / 10;
		}
		String res = String.valueOf(chas);
		StringBuilder sb = new StringBuilder(res).reverse();
		//System.out.println("res: " + res);
		if (carry != 0) {
			sb.insert(0, carry);
		}
		return sb.toString();
	}
}
